//
// Created by user on 20-4-24.
//

#include "Malloc.h"

void *kmalloc(unsigned long size, unsigned long flages) {

    int i, j;
    Slab *pSlab = NULL;

    // 1. 判断要分配的大小是否超过 1M
    if (size > 1048576) {
        printfColor(RED, BLACK, "kmalloc() ERROR: kmalloc size too long: %d\n", size);
        return NULL;
    }

    // 2. 找到符合大小的高速缓存
    for (i = 0; i < 16; i++) {
        if (kmallocCacheSize[i].size >= size)
            break;
    }

    // 3. 把找到的内存池数组内存池地址保存到临时变量里面
    pSlab = kmallocCacheSize[i].pCachePool;

    // 4. 判断当前高速缓存释放总数是否不为0，这里主要是为了找到有空闲内存的内存池，如果为0，那就再创建一个内存池
    if (kmallocCacheSize[i].totalFree != 0) {

        do {

            if (pSlab->freeCount == 0)
                pSlab = containerOf(listNext(&pSlab->list), Slab, list);
            else
                break;

        } while (pSlab != kmallocCacheSize[i].pCachePool);

    } else {

        // 1> 创建一个新的内存池
        pSlab = kmallocCreate(kmallocCacheSize[i].size);

        // 2> 判断创建内存池是否失败
        if (pSlab == NULL) {
            printfColor(BLUE, BLACK, "kmalloc()->kmalloc_create()=>slab == NULL\n");
            return NULL;
        }

        // 3> 更新内存池数组的释放总数
        kmallocCacheSize[i].totalFree += pSlab->colorCount;

        printfColor(BLUE, BLACK, "kmalloc()->kmalloc_create()<=size: %lx\n", kmallocCacheSize[i].size);

        // 4> 把新创建的内存池插入到内存数组的链表后面
        listAddToBefore(&kmallocCacheSize[i].pCachePool->list, &pSlab->list);

    }

    // 5. 遍历颜色位图，从中找到一个空闲内存对象返回给调用者
    for (j = 0; j < pSlab->colorCount; j++) {

        // 1> 判断当前颜色位图段是否可以使用，数值为 0xffffffffffffffffUL 说明已经沾满了
        if (*(pSlab->pColorMap + (j >> 6)) == 0xffffffffffffffffUL) {

            // 这段不是就换下一个
            j += 63;

            continue;

        }

        // 2> 判断者一段是否全为空
        if ((*(pSlab->pColorMap + (j >> 6)) & (1UL << (j % 64))) == 0) {

            // A. 将颜色映射位图置位
            *(pSlab->pColorMap + (j >> 6)) |= 1UL << (j % 64);

            // B. 更新使用计数和释放计数
            pSlab->usingCount++;
            pSlab->freeCount--;

            kmallocCacheSize[i].totalFree--;
            kmallocCacheSize[i].totalUsing++;

            return (void *) ((char *) pSlab->pVirtualAddress + kmallocCacheSize[i].size * j);
        }

    }

    printfColor(BLUE, BLACK, "kmalloc() ERROR: no memory can alloc\n");

    return NULL;
}

Slab *kmallocCreate(unsigned long size) {

    int i;
    Slab *pSlab = NULL;
    Page *pPage = NULL;
    unsigned long *virtualAddresss = NULL;
    long structsize = 0;

    // 1. 申请一个物理页
    pPage = allocPages(ZONE_NORMAL, 1, 0);

    // 2. 判断是否申请成功
    if (pPage == NULL) {

        printfColor(RED, BLACK, "kmalloc_create()->alloc_pages()=>page == NULL\n");

        return NULL;
    }

    // 3. 初始化物理页
    pageInit(pPage, PG_Kernel);

    // 4. 根据不同的大小创建不同大小的内存池
    switch (size) {
        ////////////////////slab + map in 2M page

        case 32:
        case 64:
        case 128:
        case 256:
        case 512:

            virtualAddresss = Physical_To_Virtual(pPage->physicalAddress);
            structsize = sizeof(Slab) + PAGE_2M_SIZE / size / 8;

            pSlab = (Slab *) ((unsigned char *) virtualAddresss + PAGE_2M_SIZE - structsize);
            pSlab->pColorMap = (unsigned long *) ((unsigned char *) pSlab + sizeof(Slab));

            pSlab->freeCount = (PAGE_2M_SIZE - (PAGE_2M_SIZE / size / 8) - sizeof(Slab)) / size;
            pSlab->usingCount = 0;
            pSlab->colorCount = pSlab->freeCount;
            pSlab->pVirtualAddress = virtualAddresss;
            pSlab->pPage = pPage;
            listInit(&pSlab->list);

            pSlab->colorLength = ((pSlab->colorCount + sizeof(unsigned long) * 8 - 1) >> 6) << 3;
            memset(pSlab->pColorMap, 0xff, pSlab->colorLength);

            for (i = 0; i < pSlab->colorCount; i++)
                *(pSlab->pColorMap + (i >> 6)) ^= 1UL << i % 64;

            break;

            ///////////////////kmalloc slab and map,not in 2M page anymore

        case 1024:        //1KB
        case 2048:
        case 4096:        //4KB
        case 8192:
        case 16384:

            //////////////////color_map is a very short buffer.

        case 32768:
        case 65536:
        case 131072:        //128KB
        case 262144:
        case 524288:
        case 1048576:        //1MB

            pSlab = (Slab *) kmalloc(sizeof(Slab), 0);

            pSlab->freeCount = PAGE_2M_SIZE / size;
            pSlab->usingCount = 0;
            pSlab->colorCount = pSlab->freeCount;

            pSlab->colorLength = ((pSlab->colorCount + sizeof(unsigned long) * 8 - 1) >> 6) << 3;

            pSlab->pColorMap = (unsigned long *) kmalloc(pSlab->colorLength, 0);
            memset(pSlab->pColorMap, 0xff, pSlab->colorLength);

            pSlab->pVirtualAddress = Physical_To_Virtual(pPage->physicalAddress);
            pSlab->pPage = pPage;

            listInit(&pSlab->list);

            for (i = 0; i < pSlab->colorCount; i++)
                *(pSlab->pColorMap + (i >> 6)) ^= 1UL << i % 64;

            break;

        default:

            printfColor(RED, BLACK, "kmalloc_create() ERROR: wrong size:%08d\n", size);
            freePages(pPage, 1);

            return NULL;
    }

    return pSlab;

}

unsigned long kfree(void *address) {

    int i;
    int index;
    Slab *pSlab = NULL;

    // 1. 计算出这个要释放的地址的页面基地址
    void *pageBaseAddress = (void *) ((unsigned long) address & PAGE_2M_MASK_CODE);

    // 2. 通过遍历找到这个基地址属于哪个高速缓存
    for (i = 0; i < 16; i++) {

        // 获取到当前Slab的指针
        pSlab = kmallocCacheSize[i].pCachePool;

        do {

            // 判断是不是这个内存池
            if (pSlab->pVirtualAddress == pageBaseAddress) {

                // 获取到当前地址的索引
                index = (int) ((address - pSlab->pVirtualAddress) / kmallocCacheSize[i].size);

                // 更新颜色位图
                *(pSlab->pColorMap + (index >> 6)) ^= 1UL << index % 64;

                pSlab->freeCount++;
                pSlab->usingCount--;

                kmallocCacheSize[i].totalFree++;
                kmallocCacheSize[i].totalUsing--;

                // 判断这个内存池是否需要销毁
                if ((pSlab->usingCount == 0) && (kmallocCacheSize[i].totalFree >= pSlab->colorCount * 3 / 2) &&
                    (kmallocCacheSize[i].pCachePool != pSlab)) {
                    switch (kmallocCacheSize[i].size) {
                        ////////////////////slab + map in 2M page

                        case 32:
                        case 64:
                        case 128:
                        case 256:
                        case 512:
                            listDel(&pSlab->list);
                            kmallocCacheSize[i].totalFree -= pSlab->colorCount;

                            pageClean(pSlab->pPage);
                            freePages(pSlab->pPage, 1);
                            break;

                        default:
                            listDel(&pSlab->list);
                            kmallocCacheSize[i].totalFree -= pSlab->colorCount;

                            kfree(pSlab->pColorMap);

                            pageClean(pSlab->pPage);
                            freePages(pSlab->pPage, 1);
                            kfree(pSlab);
                            break;
                    }

                }

                return 1;

            } else
                pSlab = containerOf(listNext(&pSlab->list), Slab, list);

        } while (pSlab != kmallocCacheSize[i].pCachePool);

    }

    printfColor(RED, BLACK, "kfree() ERROR: can`t free memory\n");

    return 0;
}